import java.util.ArrayList;
import java.util.Iterator;
import java.util.TreeMap;
import java.util.TreeSet;

import com.vividsolutions.jts.geom.GeometryFactory;
import com.vividsolutions.jts.geom.Point;
import com.vividsolutions.jts.geom.Polygon;
import com.vividsolutions.jts.io.ParseException;
import com.vividsolutions.jts.io.WKTReader;

public class IndexKNN {
	private void checkIndex(ArrayList<String> geohash,Point point,double range,int k, double x, double y) throws Exception{
		ArrayList<String> arrayList=new ArrayList<String>();
		ArrayList<String> array=new ArrayList<String>();
		TreeSet<String> indexTr=new TreeSet<String>();
		HBaseSQLDriverTest test=new HBaseSQLDriverTest();
		/*查询近似查询范围内的面数据*/
		for(int i=0;i<geohash.size();i++){
			arrayList=test.query("select geometry.getvalue from MONIINDEX where rowkey LIKE '"+geohash.get(i)+"%'");
		    array.addAll(arrayList);
		}	
		for(int i=0;i<array.size();i++){
			String string=array.get(i).substring(1,array.get(i).length()-1);
			String []strings=string.split(", ");
			for(int j=0;j<strings.length;j++){
				indexTr.add(strings[j]);
			}
		}
		String [] geoStrings=new String[indexTr.size()];
		for(int i=0;i<geoStrings.length;i++){
			geoStrings[i]=indexTr.pollFirst();
		}
		TreeMap<Double, String> GeoTreeMap=new TreeMap< Double, String>();
		System.out.println("在查询范围内的数据数："+geoStrings.length);
		/*在数据存储表中得到初步查询结果集中的面数据的坐标，计算目标点与面数据的距离
		 * 符合range条件的面数据加入GeoTreeMap中排序并输出前k个值
		 * */
		for(int i=0;i<geoStrings.length;i++){
			String polygon=test.query("select geometry.getvalue from pol where rowkey='"+geoStrings[i]+"'").get(0);
			GeometryFactory geometryFactory=new GeometryFactory();
		    WKTReader reader = new WKTReader( geometryFactory ); 
			Polygon multiPolygon=(Polygon) reader.read(polygon);
			double distance =multiPolygon.distance(point);
			if(distance<=range){
			GeoTreeMap.put(distance, geoStrings[i]);
			}
		}
		System.out.println("符合距离条件的数据数："+GeoTreeMap.size());
		if(GeoTreeMap.size()>=k){
			int i=0;
			Iterator<Double> iterator=GeoTreeMap.keySet().iterator();
			while(iterator.hasNext()){
				i++;
				if(i<=k){
					System.out.println(GeoTreeMap.get(iterator.next()));
				}
				else
					break;
			}
		}
		else{
			System.out.println("i am here");
			double latlength=range*2;
			int l=(int) (2*Math.floor(Logarithm.log(180/latlength, 2)));
			int level=l+1;
			if(level==0){
				Iterator<Double> iterator=GeoTreeMap.keySet().iterator();
				while(iterator.hasNext()){
					System.out.println(GeoTreeMap.get(iterator.next()));
				}
			}
			else{
				TreeTest.rangearrayList.clear();
				indexQueryResult(x, y, range*2, k);
			}
			
		}
		
	}
	/*得到近似于查询范围的geohash集合*/
	private ArrayList<String> searchGeohash(double X1,double Y1,double X2,double Y2) throws ParseException{
		double lonlength;
		double latlength;
		double l;
		double y,x;
		int level;
		if(X1<X2){
			lonlength=X2-X1;
		}
		else {
			lonlength=X2-X1+360;
		}
		latlength=Y2-Y1;
		if(lonlength>=latlength){
			l=(2*Math.floor(Logarithm.log(360/lonlength, 2))-1);
			y=180/(Math.pow(2, (l+1)/2));
			if(latlength<=y){
				level=(int) (l+1);
			}
			else {
				level=(int) l;
			}
		}
		else{
			l=2*Math.floor(Logarithm.log(180/latlength, 2));
			x=360/(Math.pow(2, (l+2)/2));
			if(lonlength<=x){
				level=(int) (l+1);
			}
			else{
				level=(int) l;
			}
		}
		GeometryFactory geometryFactory=new GeometryFactory();
		WKTReader reader = new WKTReader(geometryFactory);
		String rangePol="POLYGON(("+String.valueOf(X1)+" "+String.valueOf(Y1)+","+" "+String.valueOf(X1)+" "+String.valueOf(Y2)+","+" "+String.valueOf(X2)+" "+String.valueOf(Y2)+","+" "+String.valueOf(X2)+" "+String.valueOf(Y1)+","+" "+String.valueOf(X1)+" "+String.valueOf(Y1)+"))";
		Polygon polygon = (Polygon) reader.read(rangePol);
		Geohash geohash=new Geohash();
		String leftDown=geohash.encodeMaxlevel(Y1, X1, level);
		String leftUp=geohash.encodeMaxlevel(Y2, X1,level);
		String rightUp=geohash.encodeMaxlevel(Y2, X2, level);
		String rightDown=geohash.encodeMaxlevel(Y1, X2, level);
		TreeSet<String> tr = new TreeSet<String>();
		tr.add(leftDown);
		tr.add(leftUp);
		tr.add(rightUp);
		tr.add(rightDown);
		String [] geoStrings=new String[tr.size()];
		for(int i=0;i<geoStrings.length;i++){
			geoStrings[i]=tr.pollFirst();
		}
		for(int i=0;i<geoStrings.length;i++){
			if(TreeTest.Choose(polygon, geoStrings[i])){
				divRange(geoStrings[i],polygon,level);
			}			
		}
		return TreeTest.rangearrayList;		
	}
	private void divRange(String string,Polygon polygon,int level) throws ParseException {
		TreeNode root=new TreeNode();
		root=TreeTest.createTree(root,string,TreeTest.MAXSEARCHLEVEL);
		TreeTest test=new TreeTest();
		test.geohashSearchFunc(polygon,root,level);
	}
	/*基于面数据的kNN查询*/
	public void indexQueryResult(double X,double Y,double range,int k) throws Exception{
		ArrayList<String> arrayList=new ArrayList<String>();
		/*得到近似于查询范围的geohash集合*/
		arrayList=new IndexKNN().searchGeohash(X-range, Y-range, X+range, Y+range);
		String pointString="POINT"+"("+X+" "+Y+")";
		GeometryFactory geometryFactory=new GeometryFactory();
	    WKTReader reader = new WKTReader( geometryFactory );    
        Point point = (Point) reader.read(pointString); 
        /*查询包含在该范围内的面数据*/
        checkIndex(arrayList,point,range,k,X,Y);
	}
	public static void main(String []args) throws Exception{
		long startTime = System.currentTimeMillis();
		for(int i=0;i<100;i++){
			IndexKNN indexKNN=new IndexKNN();
			double X=FictitiousPolgon.getRandomNum(-180, 180);
			double Y=FictitiousPolgon.getRandomNum(-90, 90);
			indexKNN.indexQueryResult(X, Y, 3, 100);
			TreeTest.rangearrayList.clear();
		}		
		long endTime = System.currentTimeMillis();
		System.out.println("程序平均运行时间："+(endTime-startTime)/100+"ms");
	}

}
